﻿using System.Diagnostics;

namespace Graph;

//求带权图多源最短路径
//思想：动态规划法和迭代法
public class Floyd
{
    private IGraph G;

    private float[,] dis;
    private int[,] pre;

    // O（V^3）
    public Floyd(IGraph G)
    {
        this.G = G;

        dis = new float[G.V, G.V];
        pre = new int[G.V, G.V];
        for (int i = 0; i < G.V; i++)
        {
            for (int j = 0; j < G.V; j++)
            {
                dis[i, j] = i == j ? 0 : ((AdjDictionary)G).GetWeight(i, j);
                pre[i, j] = G.HasEdge(i, j) ? i : -1;
            }
        }

        for (int k = 0; k < G.V; k++) //依次考察所有顶点
        {
            for (int i = 0; i < G.V; i++)
            {
                for (int j = 0; j < G.V; j++)
                {
                    if (dis[i, k] + dis[k, j] < dis[i, j])
                    {
                        dis[i, j] = dis[i, k] + dis[k, j];
                        pre[i, j] = pre[k, j];
                    }
                }
            }
        }
    }

    public bool IsConnectedTo(int s, int t)
    {
        return dis[s, t] < float.PositiveInfinity;
    }

    public float Dis(int s, int t)
    {
        return dis[s, t];
    }

    public MyList<int> Path(int s, int t)
    {
        MyList<int> res = new MyList<int>();
        if (!IsConnectedTo(s, t))
        {
            return res;
        }

        int cur = t;
        while (cur != s)
        {
            res.Add(cur);
            cur = pre[s, cur];
        }
        res.Add(cur);

        res.Reverse();
        return res;
    }

    //验证
    static void Main(string[] args)
    {
        Stopwatch t1 = new();
        Stopwatch t2 = new();

        IGraph graph = new AdjDictionary("带权图最短路径/g.txt");

        t1.Start();
        Floyd floyd = new(graph);
        for (int s = 0; s < graph.V; s++)
        {
            for (int t = 0; t < graph.V; t++)
            {
                Console.WriteLine($"floyd:{s}->{t}: {floyd.Dis(s, t)} {floyd.Path(s, t)}");
            }
            Console.WriteLine();
        }
        t1.Stop();
        Console.WriteLine("floyd: "+t1.ElapsedMilliseconds + "ms");

        Console.WriteLine();

        t2.Start();
        for (int s = 0; s < graph.V; s++)
        {
            Dijkstra dijkstra = new(graph, s);
            for (int t = 0; t < graph.V; t++)
            {
                Console.WriteLine($"dijkstra:{s}->{t}: {dijkstra.Dis(t)} {dijkstra.Path(t)}");
            }
            Console.WriteLine();
        }
        t2.Stop();
        Console.WriteLine("dijkstra: " + t2.ElapsedMilliseconds + "ms");

        Console.Read();
    }
}
